package hashbush;

public class hashbush {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key=key;
            this.val=val;
        }
    }
    public Node[] array=new Node[10];
    public int Usesize;
    public static final double DEFAULT_FACTOR=0.75;
    public void push(int key,int val){
        int index=key%array.length;
        Node cur=array[index];
        while (cur!=null){
            //遍历链表看看k值一样不一样
            //如果一样就更新val的值
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //木有找到当前链表中有key这个节点;
        Node node=new Node(key,val);
       node.next=array[index];
        array[index]=node;
        Usesize++;
        if(double_Factor()>DEFAULT_FACTOR){
            resize();
        }
    }
    public void resize(){
        //扩容
        Node[] newarray=new Node[2*array.length];
        for (int i = 0; i <array.length ; i++) {
           Node cur=array[i];
           while (cur!=null){
               Node curN=cur.next;
               int newindex=cur.key%newarray.length;
               cur.next=newarray[newindex];
               newarray[newindex]=cur;
               cur=curN;
           }
        }
        array=newarray;
    }
    private double double_Factor(){
        return Usesize*1.0%array.length;
    }
    //获取val值
    public int get(int key){
        int index=key%array.length;
        Node cur=array[index];
        while (cur!=null){
            //遍历链表看看k值一样不一样
            //如果一样就更新val的值
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
}
